#ifndef BW_TREE_H
#define BW_TREE_H

#include "../../include/gudb.h"
#include "../memory/memory_manager.h"
#include <stdint.h>
#include <stdbool.h>
#include <stdatomic.h>
#include <pthread.h>

// Bw-Tree Configuration
#define BW_TREE_MAX_KEY_SIZE        256     // Maximum key size in bytes
#define BW_TREE_MAX_VALUE_SIZE      1024    // Maximum value size in bytes
#define BW_TREE_NODE_SIZE           4096    // Node size in bytes
#define BW_TREE_MIN_OCCUPANCY       0.5     // Minimum node occupancy ratio
#define BW_TREE_MAX_DELTA_CHAIN     8       // Maximum delta chain length before consolidation
#define BW_TREE_MAPPING_TABLE_SIZE  65536   // Initial mapping table size
#define BW_TREE_GC_EPOCH_INTERVAL   1000    // GC epoch interval in milliseconds

// Forward declarations
typedef struct bw_tree bw_tree_t;
typedef struct bw_node bw_node_t;
typedef struct delta_record delta_record_t;
typedef struct mapping_entry mapping_entry_t;
typedef struct bw_page bw_page_t;
typedef struct bw_iterator bw_iterator_t;

// Node types
typedef enum {
    BW_NODE_LEAF,
    BW_NODE_INTERNAL,
    BW_NODE_DELTA_INSERT,
    BW_NODE_DELTA_DELETE,
    BW_NODE_DELTA_UPDATE,
    BW_NODE_DELTA_SPLIT,
    BW_NODE_DELTA_MERGE,
    BW_NODE_DELTA_REMOVE,
    BW_NODE_INVALID
} bw_node_type_t;

// Key-value pair structure
typedef struct bw_kv_pair {
    uint16_t key_size;
    uint16_t value_size;
    char data[];  // Key followed by value
} bw_kv_pair_t;

// Key structure for efficient comparison
typedef struct bw_key {
    uint16_t size;
    char data[];
} bw_key_t;

// Value structure
typedef struct bw_value {
    uint16_t size;
    char data[];
} bw_value_t;

// Logical page ID type
typedef uint64_t page_id_t;

// Epoch for garbage collection
typedef uint64_t epoch_t;

// Base node structure
struct bw_node {
    bw_node_type_t type;
    uint32_t size;                  // Node size in bytes
    uint16_t count;                 // Number of key-value pairs
    uint16_t level;                 // Node level (0 for leaf, >0 for internal)
    epoch_t create_epoch;           // Epoch when node was created
    _Atomic(struct bw_node*) next;  // Next delta record in chain
    
    // For internal nodes: array of (key, page_id) pairs
    // For leaf nodes: array of (key, value) pairs
    char data[];
};

// Delta record for incremental updates
struct delta_record {
    bw_node_type_t type;            // Delta type
    uint32_t size;                  // Delta record size
    epoch_t create_epoch;           // Creation epoch
    _Atomic(struct bw_node*) next;  // Next delta in chain
    
    union {
        // Insert delta
        struct {
            bw_key_t* key;
            bw_value_t* value;
        } insert;
        
        // Delete delta
        struct {
            bw_key_t* key;
        } delete;
        
        // Update delta
        struct {
            bw_key_t* key;
            bw_value_t* old_value;
            bw_value_t* new_value;
        } update;
        
        // Split delta
        struct {
            bw_key_t* split_key;
            page_id_t new_page_id;
        } split;
        
        // Merge delta
        struct {
            page_id_t merge_page_id;
            bw_key_t* merge_key;
        } merge;
        
        // Remove delta (for node removal)
        struct {
            bool removed;
        } remove;
    } data;
};

// Physical page structure
struct bw_page {
    page_id_t page_id;              // Logical page ID
    _Atomic(bw_node_t*) node_ptr;   // Pointer to current node version
    atomic_uint ref_count;          // Reference count
    atomic_bool is_deleted;         // Deletion flag
    pthread_mutex_t mutex;          // For consolidation
    epoch_t last_access_epoch;      // Last access epoch
};

// Mapping table entry
struct mapping_entry {
    _Atomic(bw_page_t*) page;       // Pointer to physical page
    atomic_uint version;            // Version counter
};

// Mapping table structure
typedef struct mapping_table {
    size_t capacity;                // Table capacity
    size_t size;                    // Current size
    atomic_uint next_page_id;       // Next available page ID
    mapping_entry_t* entries;       // Array of mapping entries
    pthread_rwlock_t resize_lock;   // For table resizing
} mapping_table_t;

// Garbage collection context
typedef struct gc_context {
    epoch_t current_epoch;          // Current epoch
    atomic_uint active_threads;     // Number of active threads
    pthread_t gc_thread;            // GC thread
    bool gc_running;                // GC thread running flag
    pthread_mutex_t epoch_mutex;    // Epoch management mutex
    pthread_cond_t epoch_cond;      // Epoch condition variable
    
    // Deferred deletion queue
    struct gc_node {
        bw_node_t* node;
        epoch_t delete_epoch;
        struct gc_node* next;
    } *gc_queue_head, *gc_queue_tail;
    
    pthread_mutex_t gc_queue_mutex; // GC queue mutex
} gc_context_t;

// Main Bw-Tree structure
struct bw_tree {
    page_id_t root_page_id;         // Root page ID
    mapping_table_t* mapping_table; // Logical to physical mapping
    gc_context_t* gc_context;       // Garbage collection context
    memory_manager_t* memory_mgr;   // Memory manager
    
    // Statistics
    atomic_ulong total_nodes;       // Total nodes created
    atomic_ulong total_operations;  // Total operations performed
    atomic_ulong consolidations;    // Number of consolidations
    atomic_ulong splits;            // Number of splits
    atomic_ulong merges;            // Number of merges
    
    // Configuration
    uint32_t node_size;             // Node size in bytes
    double min_occupancy;           // Minimum occupancy ratio
    uint32_t max_delta_chain;       // Max delta chain length
    
    // Thread safety
    atomic_bool is_destroyed;       // Destruction flag
    atomic_uint active_operations;  // Active operations counter
};

// Iterator structure for range scans
struct bw_iterator {
    bw_tree_t* tree;               // Tree reference
    page_id_t current_page_id;     // Current page
    bw_node_t* current_node;       // Current node
    uint16_t current_index;        // Current index in node
    bw_key_t* start_key;           // Start key (inclusive)
    bw_key_t* end_key;             // End key (exclusive)
    bool forward;                  // Scan direction
    epoch_t scan_epoch;            // Scan epoch
};

// Search result structure
typedef struct bw_search_result {
    bool found;                    // Whether key was found
    bw_value_t* value;             // Found value (if any)
    page_id_t page_id;             // Page containing the key
    bw_node_t* node;               // Node containing the key
    uint16_t index;                // Index in node
} bw_search_result_t;

// Operation result codes
typedef enum {
    BW_SUCCESS = 0,
    BW_ERROR_KEY_NOT_FOUND,
    BW_ERROR_KEY_EXISTS,
    BW_ERROR_INVALID_PARAM,
    BW_ERROR_OUT_OF_MEMORY,
    BW_ERROR_NODE_FULL,
    BW_ERROR_CONCURRENT_UPDATE,
    BW_ERROR_TREE_DESTROYED
} bw_result_t;

// Core Bw-Tree API

// Tree management
bw_tree_t* bw_tree_create(memory_manager_t* memory_mgr);
void bw_tree_destroy(bw_tree_t* tree);
int bw_tree_clear(bw_tree_t* tree);

// Basic operations
bw_result_t bw_tree_insert(bw_tree_t* tree, const void* key, size_t key_size,
                          const void* value, size_t value_size);
bw_result_t bw_tree_delete(bw_tree_t* tree, const void* key, size_t key_size);
bw_result_t bw_tree_update(bw_tree_t* tree, const void* key, size_t key_size,
                          const void* value, size_t value_size);
bw_result_t bw_tree_search(bw_tree_t* tree, const void* key, size_t key_size,
                          bw_search_result_t* result);

// Conditional operations
bw_result_t bw_tree_insert_if_not_exists(bw_tree_t* tree, const void* key, size_t key_size,
                                        const void* value, size_t value_size);
bw_result_t bw_tree_update_if_exists(bw_tree_t* tree, const void* key, size_t key_size,
                                    const void* value, size_t value_size);
bw_result_t bw_tree_delete_if_exists(bw_tree_t* tree, const void* key, size_t key_size);

// Range operations
bw_iterator_t* bw_tree_scan(bw_tree_t* tree, const void* start_key, size_t start_key_size,
                           const void* end_key, size_t end_key_size, bool forward);
bool bw_iterator_valid(bw_iterator_t* iter);
bw_result_t bw_iterator_next(bw_iterator_t* iter);
bw_result_t bw_iterator_current(bw_iterator_t* iter, void** key, size_t* key_size,
                               void** value, size_t* value_size);
void bw_iterator_destroy(bw_iterator_t* iter);

// Bulk operations
bw_result_t bw_tree_bulk_insert(bw_tree_t* tree, bw_kv_pair_t** pairs, size_t count);
size_t bw_tree_range_delete(bw_tree_t* tree, const void* start_key, size_t start_key_size,
                            const void* end_key, size_t end_key_size);

// Node management (internal)
bw_node_t* bw_node_create_leaf(memory_manager_t* memory_mgr, uint32_t node_size);
bw_node_t* bw_node_create_internal(memory_manager_t* memory_mgr, uint32_t node_size);
delta_record_t* bw_delta_create_insert(memory_manager_t* memory_mgr, 
                                      const void* key, size_t key_size,
                                      const void* value, size_t value_size);
delta_record_t* bw_delta_create_delete(memory_manager_t* memory_mgr,
                                      const void* key, size_t key_size);
delta_record_t* bw_delta_create_update(memory_manager_t* memory_mgr,
                                      const void* key, size_t key_size,
                                      const void* old_value, size_t old_value_size,
                                      const void* new_value, size_t new_value_size);
void bw_node_destroy(bw_node_t* node, memory_manager_t* memory_mgr);

// Mapping table operations
mapping_table_t* mapping_table_create(size_t initial_capacity);
void mapping_table_destroy(mapping_table_t* table);
page_id_t mapping_table_allocate_page(mapping_table_t* table);
bw_page_t* mapping_table_get_page(mapping_table_t* table, page_id_t page_id);
bool mapping_table_cas_page(mapping_table_t* table, page_id_t page_id,
                           bw_node_t* expected, bw_node_t* desired);

// Node consolidation
bw_result_t bw_node_consolidate(bw_tree_t* tree, page_id_t page_id);
bool bw_node_needs_consolidation(bw_node_t* node, uint32_t max_delta_chain);
bw_node_t* bw_node_apply_deltas(bw_node_t* base_node, memory_manager_t* memory_mgr);

// Node splitting and merging
bw_result_t bw_node_split(bw_tree_t* tree, page_id_t page_id, bw_key_t* split_key);
bw_result_t bw_node_merge(bw_tree_t* tree, page_id_t left_page_id, page_id_t right_page_id);

// Garbage collection
gc_context_t* gc_context_create(void);
void gc_context_destroy(gc_context_t* gc_context);
epoch_t gc_enter_epoch(gc_context_t* gc_context);
void gc_exit_epoch(gc_context_t* gc_context);
void gc_defer_delete(gc_context_t* gc_context, bw_node_t* node);
void* gc_thread_func(void* arg);

// Utility functions
int bw_key_compare(const bw_key_t* key1, const bw_key_t* key2);
int bw_key_compare_raw(const void* key1, size_t key1_size, 
                      const void* key2, size_t key2_size);
bw_key_t* bw_key_create(memory_manager_t* memory_mgr, const void* key, size_t key_size);
bw_value_t* bw_value_create(memory_manager_t* memory_mgr, const void* value, size_t value_size);
void bw_key_destroy(bw_key_t* key, memory_manager_t* memory_mgr);
void bw_value_destroy(bw_value_t* value, memory_manager_t* memory_mgr);

// Node inspection and debugging
void bw_node_print(bw_node_t* node, int level);
size_t bw_node_get_key_count(bw_node_t* node);
size_t bw_delta_chain_length(bw_node_t* node);
bool bw_node_is_consistent(bw_node_t* node);

// Statistics and monitoring
typedef struct bw_tree_stats {
    uint64_t total_nodes;
    uint64_t leaf_nodes;
    uint64_t internal_nodes;
    uint64_t delta_records;
    uint64_t total_operations;
    uint64_t searches;
    uint64_t inserts;
    uint64_t deletes;
    uint64_t updates;
    uint64_t consolidations;
    uint64_t splits;
    uint64_t merges;
    uint64_t gc_cycles;
    double avg_delta_chain_length;
    double tree_height;
    size_t memory_usage;
} bw_tree_stats_t;

void bw_tree_get_stats(bw_tree_t* tree, bw_tree_stats_t* stats);
void bw_tree_print_stats(bw_tree_t* tree);
void bw_tree_reset_stats(bw_tree_t* tree);

// Configuration and tuning
int bw_tree_set_node_size(bw_tree_t* tree, uint32_t node_size);
int bw_tree_set_min_occupancy(bw_tree_t* tree, double min_occupancy);
int bw_tree_set_max_delta_chain(bw_tree_t* tree, uint32_t max_delta_chain);
int bw_tree_set_gc_interval(bw_tree_t* tree, uint32_t interval_ms);

// Validation and testing
bool bw_tree_validate(bw_tree_t* tree);
bool bw_tree_check_ordering(bw_tree_t* tree);
size_t bw_tree_count_keys(bw_tree_t* tree);
int bw_tree_verify_integrity(bw_tree_t* tree);

#endif // BW_TREE_H